package roman.algorithm;

import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Random;
import java.util.Scanner;

public class OnlineAlogrithm {
	Random rd = new Random(System.currentTimeMillis());
	int dataLength = 10000;
	double[] x;
	double[] y;
	int[] belongTo;
	int k = 4;
	double multiplier = 1.01;
	double f = 0.1;
	LinkedList<Integer> centers = new LinkedList<Integer>();
	
	public void clustering() throws Exception{
		double dist;
		double odist;
		shuffle();
		while(true){
			centers.clear();
			centers.add(0);
			for(int i=0; i<dataLength; i++){
				odist = Double.MAX_VALUE;
				for(int tmp : centers){
					dist = Math.sqrt((x[i]-x[tmp])*(x[i]-x[tmp])+(y[i]-y[tmp])*(y[i]-y[tmp]));
					if(odist > dist){
						odist = dist;
					}
				}
				if(odist/f > 1)
					centers.add(i);
				else{
					if(odist/f > rd.nextDouble())
						centers.add(i);
				}
				if(centers.size()>k){
					f = f*multiplier;
					break;
				}
			}
			if(centers.size()>k)
				continue;
			else
				break;
		}
	}
	public void shuffle(){
		int tmp0,tmp1;
		double tmpx,tmpy;
		tmp1 = rd.nextInt(dataLength);
		tmpx = x[0];
		tmpy = y[0];
		x[0] = x[tmp1];
		y[0] = y[tmp1];
		x[tmp1] = tmpx;
		y[tmp1] = tmpy;
		for(int i=0; i<dataLength; i++){
			tmp0 = rd.nextInt(dataLength);
			tmp1 = rd.nextInt(dataLength);
			tmpx = x[tmp0];
			tmpy = y[tmp0];
			x[tmp0] = x[tmp1];
			y[tmp0] = y[tmp1];
			x[tmp1] = tmpx;
			y[tmp1] = tmpy;
		}
	}
	public void assign(){
		int index;
		double dist,odist;
		for(int i=0; i<dataLength; i++){
			index = 0;
			odist = Double.MAX_VALUE;
			for(int tmp : centers){
				dist = Math.sqrt((x[i]-x[tmp])*(x[i]-x[tmp])+(y[i]-y[tmp])*(y[i]-y[tmp]));
				if(odist > dist){
					index=tmp;
					odist = dist;
				}
			}
			belongTo[i]=index;
		}
	}
	public void output() throws IOException{
		assign();
		PrintWriter pw1 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_1")));
		PrintWriter pw2 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_2")));
		PrintWriter pw3 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_3")));
		PrintWriter pw4 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_4")));
		for(int i=0; i<dataLength; i++){
			if(belongTo[i]==centers.get(0)){
				pw1.println("1"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[i]==centers.get(1)){
				pw2.println("2"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[i]==centers.get(2)){
				pw3.println("3"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[i]==centers.get(3)){
				pw4.println("4"+" "+x[i]+" "+y[i]);
				continue;
			}
		}
		pw1.flush();
		pw1.close();
		pw2.flush();
		pw2.close();
		pw3.flush();
		pw3.close();
		pw4.flush();
		pw4.close();
	}
	public void process() throws Exception{
		Scanner sc = new Scanner(new FileInputStream("testdata\\data0"));
		x = new double[dataLength];
		y = new double[dataLength];
		belongTo = new int[dataLength];
		int counter = 0;

		while(sc.hasNext()){
			x[counter] = sc.nextDouble();
			y[counter] = sc.nextDouble();
			counter++;
		}
		
		clustering();
		output();
		
	}
	public static void main(String[] argv) throws Exception{
		OnlineAlogrithm o = new OnlineAlogrithm();
		o.process();
	}
}
